1. Field of Use
The present invention relates to virtual memory management systems and, more particularly, to a method and an apparatus for replacing memory blocks or page frames within a virtual memory system on a least recently used (LRU) basis which minizes overhead.
2. Prior Art
A typical hierarchical structured memory system contains three levels of memory devices which differ from each other in terms of memory capacity, speed and cost. The first level contains a low capacity high-speed cache. The second level contains a slower primary or main memory while the third level contains a secondary large capacity memory storage device such as disks. When a process is to be run, its code and data are brought into primary or cache memory where the cache memory always holds the most recently used code or data. That is, the cache memory is used to store recently accessed blocks from secondary storage. The cache memory could also be part of primary memory or a separate memory between secondary and main memory.
In the above hierarchical memory structure, a memory management system is used to translate addresses and support dynamic memory allocation, support virtual memory and provide memory protection and security. It is the function of the virtual memory mechanism to allow programs to execute even when there are only a few blocks of a program residing in the primary memory while the rest of the program resides in secondary memory or disk storage.
Thus, traditional virtual memory management systems typically contain address translation mechanisms which map virtual or logical random access memory (RAM) addresses into physical RAM addresses. These mechanisms usually are included on microprocessor chips as memory management units (MMUs). Some of these mechanisms utilize associative caches organized as translation lookaside buffers (TLBs) to speed up system operations. In such designs, the TLB is used for storing information for translating a preestablished number (e.g. 16) most recently referenced pages. For each memory reference, a logical page address is compared with the address tags stored in the TLB. When a match is found, the corresponding physical page frame address is combined with an offset value from the logical address to form the physical address. When a match is not found, the processor references translation tables in main memory to automatically load the TLB. Typically, a least recently used (LRU) mechanism is used to determine which TLB entry will be replaced. For further information regarding these types of memory management architectures, reference may be made to the article entitled "A Survey of Microprocessor Architectures for Memory Management" by Borivoje Furht and Veljko Milutinovic, which appeared in the March 1987 issue of the publication, IEEE COMPUTER and to the article entitled "Microprocessor Memory Management Units" by Milan Milenkovic which appeared in the April, 1990 issue of the publication, IEEE MICRO.
When the capacity of the primary or main memory becomes exceedingly large (e.g. contain gigabytes of storage), the traditional virtual memory mechanisms are unable to adequately support virtual memory without incurring substantial overhead thereby significantly reducing overall system performance. This comes about because of the restrictions placed on limited number of entries which can reside in cache memory at any one time notwithstanding the establishment of specific thresholds used in conjunction with the cache memory's LRU mechanism for carrying out block or data entry replacement. The result is that performance slows down because the system spends much of its time swapping out useful data that it will need very shortly to bring in new data that it needs immediately. In certain situations, this can reach the thrash point where none of the processes make any progress because they keep trying to bring in the data they need and in so doing, they replace the data required by other processes.
When the number of blocks or entries are increased to accommodate increases in primary or main memory capacity, this approach has been deferred in favor of utilizing a clock like mechanism to generate reference bits which approximate the LRU mechanism. The use of thresholds and reference counts is discussed in U.S. Pat. No. 5,043,885 to John T. Robins on which issued on Aug. 27, 1991.
Thus, the above described virtual memory management systems are somewhat limited in terms of the size of the virtual address space. By contrast, a true virtual memory system is limited only by the number of address bits that the processor can generate and not by the size of available main memory on any given machine. Thus, any 32 bit system that supports virtual memory should allow program sizes of up to 4 gigabytes (2.sup.32) of the amount of its installed physical memory.
In a true virtual memory system, there is no need to relate address space to physical memory addresses. Also, a true virtual system has been regarded as a system which manages disk reads and writes for users rather than instructing the hardware to read and write data from disk each time a read or write command is issued. An example of such a system is the Pick Operating System. In this system, the data and program storage space of both RAM and disk are divided into blocks called "frames" which correspond to uniform size RAM pages containing usually 512, 1024, 2048, or, 4096 bytes. Each frame is referenced by a unique frame identifier (frame ID). Except for the utilization of a frame ID and a displacement value within such frame ID, the system does not utilize physical memory addresses or instructions which contain physical memory addresses. This eliminates the need to perform logical to physical memory address translations.
The Pick operating system has a virtual memory manager for tracking the location of data frames which works directly with disk and RAM storage. This virtual memory scheme ensures that frequently used data remains in memory as long as possible. Although this virtual memory scheme is flexible and efficient, there is the problem of allowing applications to continue to work, sometimes very slowly because of insufficient available memory or because of having to manipulate large sized files. To speed up performance of the virtual memory system, an LRU mechanism was added to the system.
While the LRU mechanism improved performance, it was discovered that way in which virtual processes are managed in terms of the allocation and deallocation of virtual memory can substantially affect overall system performance. The present invention recognizes that the traditional way of updating buffer age links when deactivating virtual processes in response process time expiration events or to page or frame faults can have a serious impact on overall system performance. More specifically, when a virtual process is deactivated because a particular frame being referenced was not in memory at the time (i.e., frame fault) or because the time interval allocated to the virtual process expired, the virtual system normally executes the required operations to bring in the requested buffer frame from secondary storage (e.g. disk) and update all of the buffer age links to indicate the location of the most recently used frame buffer. Further, the present invention recognizes that this can result in the incredible amount of valuable CPU time being expended in updating buffer age links to move buffer frames to a most recently used position even though these buffers may already be within a few locations from the most recently used position. The main reason for this is that manipulating buffer age links within main memory has proved to be a very time consuming process. Therefore, while the system performed well in the case of Pick operating system implementations, performance was notably less when Pick applications were required to run under other operating systems, such as UNIX types of operating systems.
Accordingly, it is a primary object of the present invention to provide an LRU method and mechanism which significantly enhances the performance of a virtual memory system used in a variety of different operating system environments.